package datastructure.book.tujiesuanfa.queueastack.bean;

/**
 * 最大值队列，O(1)时间复杂度获取队列最大值
 */
public class Checkout {

    int[] queue = new int[0];
    int[] maxVal = new int[0];

    public Checkout() {

    }
    /**
     * 如果队列为空，则返回 -1
     */
    public int get_max() {
        if (queue.length == 0) {
            return -1;
        } else {
            return maxVal[0];
        }
    }

    public void add(int value) {
        if (queue.length == 0) {
            queue = new int[]{value};
            maxVal = new int[]{value};
            return;
        }
        int[] tempQueue = new int[queue.length+1];
        System.arraycopy(queue,0,tempQueue,0,queue.length);
        tempQueue[tempQueue.length-1] = value;
        queue = tempQueue;
        int len = 0;
        for (int i = 0; i < maxVal.length; i++,len++) {
            if (value > maxVal[i]) {
                break;
            }
        }
        if (len == 0) {
            maxVal = new int[]{value};
        } else {
            int[] tempMaxVal = new int[len+1];
            System.arraycopy(maxVal,0,tempMaxVal,0,len);
            tempMaxVal[len] = value;
            maxVal = tempMaxVal;
        }
    }

    /**
     * 如果队列为空，则返回 -1
     */
    public int remove() {
        if (queue.length == 0) {
            return -1;
        }
        int[] tempQueue = new int[queue.length-1];
        System.arraycopy(queue,1,tempQueue,0,queue.length-1);
        int result = queue[0];
        queue = tempQueue;
        if (result == maxVal[0]) {
            int[] tempMaxVal = new int[maxVal.length-1];
            System.arraycopy(maxVal,1,tempMaxVal,0,maxVal.length-1);
            maxVal = tempMaxVal;
        }
        return result;
    }
}
